| 翻訳と辞書 |
| Adaptive sort ： ウィキペディア英語版 |
Adaptive sort
A sorting algorithm falls into the adaptive sort family if it takes advantage of existing order in its input. It benefits from the presortedness in the input sequence – or a limited amount of disorder for various definitions of measures of disorder – and sorts faster. Adaptive sorting is usually performed by modifying existing sorting algorithms.
== Motivation ==
Comparison-based sorting algorithms have traditionally dealt with achieving an optimal bound of ''O(n ''log'' n)'' when dealing with time complexity. Adaptive sort takes advantage of the existing order of the input to try to achieve better times, so that the time taken by the algorithm to sort is a smoothly growing function of the size of the sequence ''and'' the disorder in the sequence. In other words, the more presorted the input is, the faster it should be sorted.
This is an attractive algorithm because nearly sorted sequences are common in practice. Thus, the performance of existing sort algorithms can be improved by taking into account the existing order in the input.
Note that the most worst-case sorting algorithms that do optimally well in the worst-case, notably heap sort and merge sort, do not take existing order within their input into account, although this deficiency is easily rectified in the case of merge sort by checking if left.last_item ≤ right.first_item, in which case a merge operation may be replaced by simple concatenation – a modification that is well within the scope of making an algorithm adaptive.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Adaptive sort」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|